package leetcode_acm.leetcode_1;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月17日 10:26
 */
public class CountSmaller {
    private class Pair{
        int index;
        int val;

        public Pair(int index, int val) {
            this.index = index;
            this.val = val;
        }
    }

    private Pair[] memo;
    private int[] count;

    public List<Integer> countSmaller(int[] nums) {
        memo = new Pair[nums.length];
        count = new int[nums.length];
        Pair[] pairs = new Pair[nums.length];
        for (int i = 0; i < nums.length; i++) {
            pairs[i] = new Pair(i,nums[i]);
        }
        sort(pairs,0, pairs.length-1);
        List<Integer> list = new ArrayList<>(nums.length);
        return list;
    }

    private void sort(Pair[] nums,int l,int r){
        if(l >= r){
            return;
        }
        int mid = (l+((r-l)>>1));
        sort(nums,l,mid);
        sort(nums,mid+1,r);
        merge(nums,l,mid,r);
    }

    private void merge(Pair[] nums,int l,int mid,int r){
        if (r + 1 - l >= 0) {
            System.arraycopy(nums, l, memo, l, r + 1 - l);
        }
        int i = l;int j = mid+1;
        for(int p = l;p <= r;p++){
            if(i == mid+1){
                nums[p] = memo[j++];
            }else if(j == r + 1){
                nums[p] = memo[i++];
                //r-mid-1+1
                count[nums[p].index] += r-mid;
            }else if(memo[i].val <= memo[j].val){
                nums[p] = memo[i++];
                //j-1-mid-1+1
                count[nums[p].index] += j-mid-1;
            }else{
                nums[p] = memo[j++];
            }
        }
    }
}
